package com.leetcode;

import com.leetcode.entity.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 从尾部开始依次打印链表节点
 */
public class Offer06 {

    public static void main(String[] args) {
        // TODO 1,2,3,4,5,6,7,8,9,10
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11, 10, 2, 4,8,9,87};
        ListNode head = new ListNode(1);
        ListNode tmp = head;
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            tmp.next = new ListNode(nums[i]);
            tmp = tmp.next;
        }

//        // TODO 链表反转
//        ListNode tailNode = inverted(head);
//        StringBuilder sb = new StringBuilder("");
//        while (tailNode != null) {
//            sb.append(tailNode.val + ",");
//            tailNode = tailNode.next;
//        }
//        System.out.println(sb.toString());

//        // TODO 使用Stack进行处理
//        toStack(head);

        // TODO 递归处理
        int[] result = new int[len];
        recursive(head, result, len - 1);
        printNums(result);
    }

    /**
     * 返回从尾部开始的节点值
     * @param head
     * @return
     */
    public static List<Integer> toList(ListNode head) {
        ListNode tmp = head;
        List<Integer> list = new ArrayList<>();
        while (tmp != null) {
            list.add(tmp.val);
            tmp = tmp.next;
        }
        return list;
    }

    /**
     * 逆转链表
     * @param head
     * @return
     */
    public static ListNode inverted(ListNode head) {
        ListNode tail = null;
        ListNode tmp = null;
        while (head != null) {
            tmp = head.next;
            head.next = tail;
            tail = head;
            head = tmp;
        }
        return tail;
    }

    /**
     * 根据先入后出的原则，使用栈来进行处理
     * @param head
     */
    public static void toStack(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode tmp = head;
        while (tmp != null) {
            stack.push(tmp.val);
            tmp = tmp.next;
        }

        int size = stack.size();
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < size; i++) {
            sb.append(stack.pop() + ",");
        }
        System.out.println(sb.toString());
    }

    /**
     * 递归算法
     * @param node
     * @param nums
     * @param index
     */
    public static void recursive(ListNode node, int[] nums, int index) {
        if (node == null)
            return;
        nums[index] = node.val;
        recursive(node.next, nums, index - 1);
    }

    /**
     * 打印数组
     * @param nums
     */
    public static void printNums(int[] nums) {
        StringBuilder sb = new StringBuilder("");
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            sb.append(nums[i] + ",");
        }
        System.out.println(sb.toString());
    }
}
